{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Good Binary Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: goodBinaryStrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #好二进制字符串的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><span style=\"\">给你四个整数 </span><code>minLenght</code>、<code>maxLength</code>、<code>oneGroup</code><span style=\"\"> 和 </span><code>zeroGroup</code><span style=\"\"> 。</span></p>\n",
    "\n",
    "<p><strong>好 </strong>二进制字符串满足下述条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符串的长度在 <code>[minLength, maxLength]</code> 之间。</li>\n",
    "\t<li>每块连续 <code>1</code> 的个数是 <code>oneGroup</code> 的整数倍\n",
    "\t<ul>\n",
    "\t\t<li>例如在二进制字符串 <code>00<em><strong>11</strong></em>0<em><strong>1111</strong></em>00</code> 中，每块连续 <code>1</code> 的个数分别是<code>[2,4]</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>每块连续 <code>0</code> 的个数是 <code>zeroGroup</code> 的整数倍\n",
    "\t<ul>\n",
    "\t\t<li>例如在二进制字符串 <code><em><strong>00</strong></em>11<em><strong>0</strong></em>1111<em><strong>00</strong></em></code> 中，每块连续 <code>0</code> 的个数分别是 <code>[2,1,2]</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>请返回好二进制字符串的个数。答案可能很大<strong>，</strong>请返回对 <code>10<sup>9</sup> + 7</code> 取余后的结果。</p>\n",
    "\n",
    "<p><strong>注意：</strong><code>0</code> 可以被认为是所有数字的倍数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>minLength = 2, maxLength = 3, oneGroup = 1, zeroGroup = 2\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>在本示例中有 5 个好二进制字符串: \"00\", \"11\", \"001\", \"100\", 和 \"111\" 。\n",
    "可以证明只有 5 个好二进制字符串满足所有的条件。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>minLength = 4, maxLength = 4, oneGroup = 4, zeroGroup = 3\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>在本示例中有 1 个好二进制字符串: \"1111\" 。\n",
    "可以证明只有 1 个好字符串满足所有的条件。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= minLength &lt;= maxLength &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= oneGroup, zeroGroup &lt;= maxLength</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-good-binary-strings](https://leetcode.cn/problems/number-of-good-binary-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-good-binary-strings](https://leetcode.cn/problems/number-of-good-binary-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3\\n1\\n2', '4\\n4\\n4\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "# from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        aa, bb = minLength - 1, maxLength - 1\n",
    "        dp = [0 for i in range(1+bb)]\n",
    "\n",
    "        for i in range(bb+1):\n",
    "            dp[i] = 0\n",
    "\n",
    "            pre = i - oneGroup\n",
    "            if pre == -1:\n",
    "                dp[i] += 1\n",
    "            else:\n",
    "                if pre >= 0:\n",
    "                    dp[i] += dp[pre]\n",
    "\n",
    "\n",
    "            pre = i - zeroGroup\n",
    "            if pre == -1:\n",
    "                dp[i] += 1\n",
    "            else:\n",
    "                if pre >= 0:\n",
    "                    dp[i] += dp[pre]\n",
    "\n",
    "            dp[i] %= MOD\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(aa, bb+1):\n",
    "            ans += dp[i]\n",
    "            ans %= MOD\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        # dp[i][j]: number of binary strings has length i\n",
    "        dp = [0] * (maxLength+1)\n",
    "        dp[0] = 1\n",
    "        MOD = int(1e9+7)\n",
    "        anw = 0\n",
    "        for i in range(1, maxLength+1):\n",
    "            if i >= zeroGroup:\n",
    "                dp[i] += (dp[i-zeroGroup] % MOD)\n",
    "            if i >= oneGroup:\n",
    "                dp[i] += (dp[i-oneGroup] % MOD)\n",
    "            if i >= minLength:\n",
    "                anw += (dp[i] % MOD)\n",
    "        return anw % MOD\n",
    "        # dp = [[0,0] for _ in range(maxLength+1)]\n",
    "        # dp[0][0] = 1\n",
    "        # dp[0][1] = 1\n",
    "        # MOD = int(1e9+7)\n",
    "        # for i in range(1, maxLength+1):\n",
    "        #     if i >= zeroGroup:\n",
    "        #         dp[i][0] += (dp[i-zeroGroup][0] % MOD)\n",
    "        #         dp[i][0] += (dp[i-zeroGroup][1] % MOD)\n",
    "        #     if i >= oneGroup:\n",
    "        #         dp[i][1] += (dp[i-oneGroup][1] % MOD)\n",
    "        #         dp[i][1] += (dp[i-oneGroup][0] % MOD)\n",
    "        # print(dp)\n",
    "        # anw = 0\n",
    "        # for i in range(minLength, maxLength+1):\n",
    "        #     anw += dp[i][0] % MOD\n",
    "        #     anw += dp[i][1] % MOD\n",
    "\n",
    "        # return anw #(sum(dp[minLength:maxLength+1][0]) + sum(dp[minLength:maxLength+1][1])) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        a, b, has, sm = min(oneGroup, zeroGroup), max(oneGroup, zeroGroup), [1], 0\n",
    "        for i in range(1, maxLength+1):\n",
    "            has.append(0)\n",
    "            if i >= a:\n",
    "                has[-1] += has[i-a]\n",
    "                if i >= b:\n",
    "                    has[-1] = (has[-1] + has[i-b]) % 1000000007\n",
    "            if i >= minLength: sm = (sm + has[-1]) % 1000000007\n",
    "        return sm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dp\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        dp = [0] * (maxLength + 1)\n",
    "        dp[0] = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, maxLength + 1) :\n",
    "            if i - zeroGroup >= 0 :\n",
    "                dp[i] += dp[i - zeroGroup]\n",
    "\n",
    "            if i - oneGroup >= 0 :\n",
    "                dp[i] += dp[i - oneGroup]\n",
    "\n",
    "            dp[i] %= mod\n",
    "\n",
    "        return sum(dp[minLength : maxLength + 1]) % mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        '''output = 0\n",
    "        multiplier0 = 1\n",
    "        #multiplier1 = 0\n",
    "\n",
    "        for i in range(minLength, maxLength + 1):\n",
    "\n",
    "            if i % zeroGroup == 0:\n",
    "                output += 1\n",
    "\n",
    "            if i % oneGroup == 0:\n",
    "                output += 1\n",
    "\n",
    "            while multiplier0 * zeroGroup <= i:\n",
    "\n",
    "                if (i - multiplier0 * zeroGroup) % oneGroup == 0:\n",
    "                    \n",
    "                    \n",
    "\n",
    "                multiplier0 += 1\n",
    "        \n",
    "        return output'''\n",
    "\n",
    "        dp = [0 for _ in range(maxLength + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1,maxLength + 1):\n",
    "            dp[i] = dp[i] + (dp[i - oneGroup] if i - oneGroup >= 0 else 0)\n",
    "            dp[i] = dp[i] + (dp[i - zeroGroup] if i - zeroGroup >= 0 else 0)\n",
    "            dp[i] %= (10 ** 9 + 7)\n",
    "        return sum(dp[minLength:]) % (10 ** 9 + 7) \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        # copy answer, don't want to write\n",
    "        dp = [0 for _ in range(maxLength + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1,maxLength + 1):\n",
    "            dp[i] = dp[i] + (dp[i - oneGroup] if i - oneGroup >= 0 else 0)\n",
    "            dp[i] = dp[i] + (dp[i - zeroGroup] if i - zeroGroup >= 0 else 0)\n",
    "            dp[i] %= (10 ** 9 + 7)\n",
    "        return sum(dp[minLength:]) % (10 ** 9 + 7) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        a, b, has, sm = min(oneGroup, zeroGroup), max(oneGroup, zeroGroup), [1] + [0] * maxLength, 0\n",
    "        for i in range(a, maxLength+1):\n",
    "            has[i] = (has[i-a] + has[i-b]) % 1000000007 if i >= b else has[i-a]\n",
    "            if i >= minLength: sm = (sm + has[i]) % 1000000007\n",
    "        return sm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        nums = [0 for _ in range(maxLength+1)]\n",
    "        nums[0] = 1\n",
    "        for i in range(1, maxLength+1):\n",
    "            if i-oneGroup>=0:\n",
    "                nums[i] += nums[i-oneGroup]\n",
    "            if i-zeroGroup>=0:\n",
    "                nums[i] += nums[i-zeroGroup]\n",
    "            nums[i] = nums[i]%(10**9+7)\n",
    "        # print(nums)\n",
    "        return sum(nums[minLength:maxLength+1])%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        a, b, has = min(oneGroup, zeroGroup), max(oneGroup, zeroGroup), [1]\n",
    "        for i in range(maxLength):\n",
    "            has.append(0)\n",
    "            if i + 1 >= a:\n",
    "                has[-1] += has[i+1-a]\n",
    "                if i + 1 >= b:\n",
    "                    has[-1] = (has[-1] + has[i+1-b]) % 1000000007\n",
    "        return sum(has[minLength:maxLength+1]) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def goodBinaryStrings(self, minLength, maxLength, oneGroup, zeroGroup):\n",
    "        dp = [0] * (maxLength + 1)\n",
    "        dp[0] = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, maxLength + 1) :\n",
    "            if i - zeroGroup >= 0 :\n",
    "                dp[i] += dp[i - zeroGroup]\n",
    "            if i - oneGroup >= 0 :\n",
    "                dp[i] += dp[i - oneGroup]\n",
    "            dp[i] %= mod\n",
    "        return sum(dp[minLength : maxLength + 1]) % mod\n",
    "        \n",
    "\n",
    "    def goodBinaryStrings2(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        dp = [0 for _ in range(maxLength + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1,maxLength + 1):\n",
    "            dp[i] = dp[i] + (dp[i - oneGroup] if i - oneGroup >= 0 else 0)\n",
    "            dp[i] = dp[i] + (dp[i - zeroGroup] if i - zeroGroup >= 0 else 0)\n",
    "            dp[i] %= (10 ** 9 + 7)\n",
    "        return sum(dp[minLength:]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "\n",
    "        dp = [1] + [0]*maxLength\n",
    "        mod = 10**9 +7\n",
    "\n",
    "        for a in range (1, maxLength +1):\n",
    "            if a >= oneGroup:\n",
    "                dp[a] = dp[a]+ dp[a-oneGroup]\n",
    "            if a >= zeroGroup:\n",
    "                dp[a] = dp[a]+ dp[a-zeroGroup]\n",
    "            dp[a] %= mod\n",
    "\n",
    "        k = sum(dp[minLength:]) % mod\n",
    "\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        dp = [0] * (maxLength + 1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, maxLength + 1):\n",
    "            if i - oneGroup >= 0:\n",
    "                dp[i] += dp[i-oneGroup]\n",
    "            if i - zeroGroup >= 0:\n",
    "                dp[i] += dp[i-zeroGroup]\n",
    "            \n",
    "            dp[i] %= (10 ** 9 + 7)\n",
    "\n",
    "        return sum(dp[minLength: maxLength+1]) % (10 ** 9 + 7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        '''output = 0\n",
    "        multiplier0 = 1\n",
    "        #multiplier1 = 0\n",
    "\n",
    "        for i in range(minLength, maxLength + 1):\n",
    "\n",
    "            if i % zeroGroup == 0:\n",
    "                output += 1\n",
    "\n",
    "            if i % oneGroup == 0:\n",
    "                output += 1\n",
    "\n",
    "            while multiplier0 * zeroGroup <= i:\n",
    "\n",
    "                if (i - multiplier0 * zeroGroup) % oneGroup == 0:\n",
    "                    \n",
    "                    \n",
    "\n",
    "                multiplier0 += 1\n",
    "        \n",
    "        return output'''\n",
    "\n",
    "        dp = [0 for _ in range(maxLength + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1,maxLength + 1):\n",
    "            dp[i] = dp[i] + (dp[i - oneGroup] if i - oneGroup >= 0 else 0)\n",
    "            dp[i] = dp[i] + (dp[i - zeroGroup] if i - zeroGroup >= 0 else 0)\n",
    "            dp[i] %= (10 ** 9 + 7)\n",
    "        return sum(dp[minLength:]) % (10 ** 9 + 7) \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        f = [0] * (maxLength + 1)\n",
    "        f[0] = 1         # 题干: Note that 0 is considered a multiple of all the numbers.\n",
    "\n",
    "        for i in range(1, maxLength + 1):         # 分情况讨论\n",
    "            if i - oneGroup >= 0:\n",
    "                f[i] += f[i - oneGroup]           # 闭区间[i - oneGroup + 1: i] 范围全为 1 \n",
    "            if i - zeroGroup >= 0:\n",
    "                f[i] += f[i - zeroGroup]          # 闭区间[i - zeroGroup + 1: i] 范围全为 0 \n",
    "            f[i] %= (10 ** 9 + 7)\n",
    "\n",
    "        return sum(f[minLength: maxLength + 1]) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        dp=[0 for _ in range(maxLength+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,maxLength+1):\n",
    "            dp[i]=dp[i]+(dp[i-oneGroup] if i>=oneGroup else 0) \n",
    "            dp[i]=dp[i]+(dp[i-zeroGroup] if i>=zeroGroup else 0)\n",
    "            dp[i]=dp[i]% (10**9+7)\n",
    "        print(dp)\n",
    "        return(sum(dp[minLength:])%(10**9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, mn: int, mx: int, a: int, b: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n == 0: return 1\n",
    "            if n < 0: return 0\n",
    "            return (f(n-a) + f(n-b)) % MOD\n",
    "        ans = 0\n",
    "        for i in range(mn, mx+1):\n",
    "            ans += f(i)\n",
    "            ans %= MOD\n",
    "        f.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "sys.setrecursionlimit(99999)\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        \"\"\"\n",
    "        :param minLength:\n",
    "        :param maxLength:\n",
    "        :param oneGroup:\n",
    "        :param zeroGroup:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def get_ans(cur_len):\n",
    "            mod1 = 10**9+7\n",
    "            ans = 0\n",
    "            if cur_len == 0:\n",
    "                return 1\n",
    "            if cur_len - zeroGroup >= 0:\n",
    "                ans += get_ans(cur_len - zeroGroup)\n",
    "            if cur_len - oneGroup >= 0:\n",
    "                ans += get_ans(cur_len - oneGroup)\n",
    "            ans %= mod1\n",
    "            return ans\n",
    "\n",
    "        mod1 = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        for i in range(minLength, maxLength+1):\n",
    "            res += get_ans(i) % mod1\n",
    "        return res % mod1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "sys.setrecursionlimit(99999)\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        \"\"\"\n",
    "        :param minLength:\n",
    "        :param maxLength:\n",
    "        :param oneGroup:\n",
    "        :param zeroGroup:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def get_ans(cur_len):\n",
    "            mod1 = 10**9+7\n",
    "            ans = 0\n",
    "            if cur_len == 0:\n",
    "                return 1\n",
    "            if cur_len - zeroGroup >= 0:\n",
    "                ans += get_ans(cur_len - zeroGroup)\n",
    "            if cur_len - oneGroup >= 0:\n",
    "                ans += get_ans(cur_len - oneGroup)\n",
    "            ans %= mod1\n",
    "            return ans\n",
    "\n",
    "        mod1 = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        for i in range(minLength, maxLength+1):\n",
    "            res += get_ans(i) % mod1\n",
    "        return res % mod1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        \"\"\" DP: climbing stairs. \n",
    "        either climb multiple oneGroup or multiple zeroGroups\n",
    "        so dfs(maxlength): all the possible combinations up to maxlength \n",
    "        so the return will be dfs(maxlength) - dfs(minlength-1)\n",
    "        \"\"\"\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(stairs):\n",
    "            if stairs <= 0:\n",
    "                return 0\n",
    "\n",
    "            ans = 0\n",
    "            if stairs - oneGroup >= 0:\n",
    "                ans += dfs(stairs - oneGroup) + 1\n",
    "                ans %= int(10**9 + 7)\n",
    "            if stairs - zeroGroup >= 0:\n",
    "                ans += dfs(stairs - zeroGroup) + 1\n",
    "                ans %= int(10**9 + 7)\n",
    "            \n",
    "            return ans \n",
    "\n",
    "        return (dfs(maxLength) - dfs(minLength-1)) % int(10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(cur_n):\n",
    "            if cur_n > maxLength:\n",
    "                return 0\n",
    "            tmp = int(cur_n >= minLength)\n",
    "\n",
    "            tmp += dfs(cur_n + oneGroup) % MOD\n",
    "            tmp += dfs(cur_n + zeroGroup) % MOD\n",
    "            return tmp % MOD\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        if zeroGroup<oneGroup:\n",
    "            oneGroup,zeroGroup = zeroGroup,oneGroup\n",
    "        dp = [0]*(maxLength+1)\n",
    "        dp[0] = 1\n",
    "        s = 0\n",
    "        rem = 10**9+7\n",
    "        dp[oneGroup]=1\n",
    "        dp[zeroGroup]+=1\n",
    "        for i in range(1,maxLength+1):\n",
    "            if i>oneGroup:\n",
    "                dp[i] += dp[i-oneGroup]*2\n",
    "                if i>=2*oneGroup:\n",
    "                    dp[i] -= dp[i-2*oneGroup]\n",
    "                dp[i] = dp[i]%rem\n",
    "            if i>zeroGroup:\n",
    "                dp[i] += dp[i-zeroGroup]*2\n",
    "                if i>=2*zeroGroup:\n",
    "                    dp[i] -= dp[i-2*zeroGroup]\n",
    "                dp[i] = dp[i]%rem\n",
    "            if i>=zeroGroup+oneGroup:\n",
    "                dp[i] -= dp[i-zeroGroup-oneGroup]*2\n",
    "            if i>=minLength:\n",
    "                s = (s+dp[i])%rem\n",
    "        # print(dp)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        dp = [0] * (maxLength + 1)\n",
    "        ans = 0\n",
    "        for i in range(maxLength + 1):\n",
    "            if i == oneGroup:\n",
    "                dp[i] += 1\n",
    "            if i == zeroGroup:\n",
    "                dp[i] += 1\n",
    "            r0 = dp[i - zeroGroup] if i > zeroGroup else 0\n",
    "            r1 = dp[i - oneGroup] if i > oneGroup else 0\n",
    "            dp[i] = r0 + r1 + dp[i]\n",
    "            if i >= minLength:\n",
    "                ans += dp[i]\n",
    "        return ans % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        '''output = 0\n",
    "        multiplier0 = 1\n",
    "        #multiplier1 = 0\n",
    "\n",
    "        for i in range(minLength, maxLength + 1):\n",
    "\n",
    "            if i % zeroGroup == 0:\n",
    "                output += 1\n",
    "\n",
    "            if i % oneGroup == 0:\n",
    "                output += 1\n",
    "\n",
    "            while multiplier0 * zeroGroup <= i:\n",
    "\n",
    "                if (i - multiplier0 * zeroGroup) % oneGroup == 0:\n",
    "                    \n",
    "                    \n",
    "\n",
    "                multiplier0 += 1\n",
    "        \n",
    "        return output'''\n",
    "\n",
    "        dp = [0 for _ in range(maxLength + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1,maxLength + 1):\n",
    "            dp[i] = dp[i] + (dp[i - oneGroup] if i - oneGroup >= 0 else 0)\n",
    "            dp[i] = dp[i] + (dp[i - zeroGroup] if i - zeroGroup >= 0 else 0)\n",
    "            #dp[i] %= (10 ** 9 + 7)\n",
    "        return sum(dp[minLength:]) % (10 ** 9 + 7) \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:\n",
    "        '''output = 0\n",
    "        multiplier0 = 1\n",
    "        #multiplier1 = 0\n",
    "\n",
    "        for i in range(minLength, maxLength + 1):\n",
    "\n",
    "            if i % zeroGroup == 0:\n",
    "                output += 1\n",
    "\n",
    "            if i % oneGroup == 0:\n",
    "                output += 1\n",
    "\n",
    "            while multiplier0 * zeroGroup <= i:\n",
    "\n",
    "                if (i - multiplier0 * zeroGroup) % oneGroup == 0:\n",
    "                    \n",
    "                    \n",
    "\n",
    "                multiplier0 += 1\n",
    "        \n",
    "        return output'''\n",
    "\n",
    "        dp = [0 for _ in range(maxLength + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1,maxLength + 1):\n",
    "            dp[i] = dp[i] + (dp[i - oneGroup] if i - oneGroup >= 0 else 0)\n",
    "            dp[i] = dp[i] + (dp[i - zeroGroup] if i - zeroGroup >= 0 else 0)\n",
    "            #dp[i] %= (10 ** 9 + 7)\n",
    "        return sum(dp[minLength:]) % (10 ** 9 + 7) \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
